package com.atguigu.huffmantree.code;

import java.lang.reflect.Array;
import java.util.*;

/**
 * @author durant
 * @create 2021-11-18 9:27
 */
public class HuffmanCode {
    public static void main(String[] args) {

        String str = "i like like like java do you like a java";
        byte[] bytes = autoZip(str);
        System.out.println(Arrays.toString(bytes));

        byte[] huffmanCodeBytes = zip(bytes, huffmanCode);
        byte[] decode = decode(huffmanCode, huffmanCodeBytes);
        System.out.println("原来的字符串：" + Arrays.toString(decode));

    }

    // 封装方法
    public static byte[] autoZip(String str) {
        byte[] contentBytes = str.getBytes();
        List<Node> nodes = getNodes(contentBytes);
        // 创建赫夫曼树
        Node huffman = createHuffman(nodes);
        // 生成对应的赫夫曼编码
        getCodes(huffman);
        System.out.println("huffmancode：" + huffmanCode);// 修改前{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
        decode(huffmanCode, zip(contentBytes, huffmanCode));
        return zip(contentBytes, huffmanCode);

    }

    /**
     * @param ：bytes       原始字符串对应的数组
     * @param ：huffmanCode 生成的赫夫曼编码
     * @return ：byte       处理后的数组
     * @Description ： 压缩
     * @Author ：Durant
     * @Date ：2021/11/18 10:53
     * 返回的是字符串1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
                 * 1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
                   101010001011111111001000101111111100100010111111110010010100110111000111000001101110100011110010100010111111110011000100101001100
    赫夫曼解码后的字节数组转对应的二进制字符串：
     * 8位对应一个byte，放入到huffmanCodeBytes中
     * huffmanCode[0]=10101000(补码) => byte 10101000 - 1 = 10100111 (反码)=>11011000==-88
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCode) {
        // 先使用huffmanCode 将原始的byte数组转成赫夫曼编码的byte数组
        // 需要用到builder进行拼接
        StringBuilder stringBuilder = new StringBuilder();
        // 遍历byte数组
        for (byte b : bytes) {
            stringBuilder.append(huffmanCode.get(b));
        }
        // 将这个字符串转成byte数组
        // 统计返回的byte[] huffmanCodeBytes长度
        int length;
        if (stringBuilder.length() % 8 == 0) {
            length = stringBuilder.length() / 8;
        } else {
            length = 1 + stringBuilder.length() / 8;
        }
        // 创建存储压缩后的byte数组
        byte[] huffmanCodeBytes = new byte[length];
        int index = 0;
        for (int i = 8; i < stringBuilder.length(); i += 8) {// 因为是每8位对应一个byte
            String strByte;
            strByte = stringBuilder.substring(i - 8, i);
            huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;
        }
        return huffmanCodeBytes;
    }

    public static List<Node> getNodes(byte[] bytes) {
        // 1.创建一个arraylist
        List<Node> nodes = new ArrayList<>();

        // 遍历，存储每一个byte出现的次数，使用map
        Map<Byte, Integer> counts = new HashMap<>();// key是数据，value是权重
        for (byte b : bytes) {
            Integer count = counts.get(b);
            if (count == null) {
                counts.put(b, 1);
            } else {
                counts.put(b, count + 1);
            }

        }
        // map中数据构建完成后，构建node
        // 把每个键值对转成node对象，并加入到nodes集合
        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }

    private static Node createHuffman(List<Node> nodes) {
        while (nodes.size() > 1) {// 大于1时排序
            Collections.sort(nodes);
            // 取出最小的数
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            // 构建父子树,没有data，只有权值
            Node parent = new Node(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parent);
        }
        //
        return nodes.get(0);
    }

    // 前序遍历
    public static void preOrder(Node root) {
        if (root != null) {
            root.preList();
        } else {
            System.out.println("节点为空，不能遍历");
        }
    }

    // 根据赫夫曼树生成赫夫曼编码表
    // 思路：
    // 1.将编码表存放在map中比较合适
    // 32=01 97=100 100=11000 u=11001 e=1110 v=11011 i=101 y=11010 j=0010 k=1111 l=000 o=0011
    // 2.在创建编码表时需要不断地去拼接路径，定义一个stringbuilder,例如0+0+0+1 = 0001
    static StringBuilder builder = new StringBuilder();
    static Map<Byte, String> huffmanCode = new HashMap<>();

    /**
     * @param ：node          将node传入的叶子节点的赫夫曼编码得到，并放到huffmanCode中
     * @param ：code          代表路径，0代表走左边，1代表走右边
     * @param ：stringBuilder 对路径进行拼接
     * @return ：void
     * @Description ： 获得赫夫曼编码
     * @Author ：Durant
     * @Date ：2021/11/18 10:18
     */
    private static Map<Byte, String> getCodes(Node node) {
        if (node == null) {
            return null;
        }
        getCodes(node, "", builder);
        return huffmanCode;
    }

    private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        // 将code加入到stringbuilder
        stringBuilder2.append(code);
        if (node != null) {
            // 判断是叶子节点还是非叶子节点，叶子节点的data不等于null
            if (node.data == null) {
                // 向左走
                getCodes(node.left, "0", stringBuilder2);
                // 向右走
                getCodes(node.right, "1", stringBuilder2);
            } else { // node.data != null 说明是叶子节点
                // 这个递归就可以停止了
                huffmanCode.put(node.data, stringBuilder2.toString());
            }
        }
    }
    // 数据解压
    // 1.将[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 0] 转成对应二进制的字符串
    // 2.将二进制字符串根据赫夫曼编码转成字符

    // 将一个byte转换成二进制字符串

    /**
     * @param ：flag 表示是否需要补高位，如果是false表示不需要
     * @param ：b    表示对应的二进制字符串
     * @return ：String
     * @Description ：
     * @Author ：Durant
     * @Date ：2021/11/18 12:29
     */
    private static String bytesToBitString(boolean flag, byte b) {
        int temp = b;
        if (flag) {
            temp |= 256;
        }
        String str = Integer.toBinaryString(temp);// 返回的是二进制的补码
        if (flag) {
            return str.substring(str.length() - 8);// 截取需要的长度
        } else {
            return str;
        }
    }

    /**
     * @param ：huffmanCodes 哈夫曼编码
     * @param ：huffmanBytes 是需要解码的字节数组
     * @return ：byte  返回的是原来字符串对应的数组
     * @Description ： 完成对压缩数据的解码
     * @Author ：Durant
     * @Date ：2021/11/18 12:31
     */
    private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
        // 1.先得到huffmanBytes对应的二进制字符串，
        StringBuilder stringBuilder = new StringBuilder();
        // 将byte数组转成二进制的字符串
        for (int i = 0; i < huffmanBytes.length;) {
            // 判断是不是最后一个字节
            boolean flag = (i == huffmanBytes.length - 1);
            stringBuilder.append(bytesToBitString(!flag, huffmanBytes[i]));
        }
        System.out.println("赫夫曼解码后的字节数组转对应的二进制字符串："+stringBuilder.toString());
        // 把字符串按照赫夫曼编码表进行解码,将编码表进行反转
        Map<String,Byte> reverseMap =new HashMap<>();
        for(Map.Entry<Byte,String> map : huffmanCodes.entrySet() ){
           reverseMap.put(map.getValue(), map.getKey());
        }
        // 创建要给的集合，存放byte
        List<Byte> list = new ArrayList<>();
        for (int i = 0; i < stringBuilder.length(); i++) {
            int count =1;
            boolean flag = true;
            while (flag){
                String key = stringBuilder.substring(i,i+count);
                if (reverseMap.get(key) != null){
                    list.add(Byte.parseByte(key));
                    flag = false;
                }
                count ++;
            }
            i +=count;
        }
        byte[] b = new byte[list.size()];
        for (int i = 0; i < list.size(); i++) {
            b[i] = list.get(i);
        }
        return b;
    }
}

// 创建node节点
class Node implements Comparable<Node> {
    Byte data;
    int weight;
    Node left;
    Node right;


    @Override
    public String toString() {
        return "Node{" + "data=" + data + ", weight=" + weight + '}';
    }

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;// 从小到大排列
    }

    // 前序遍历
    public void preList() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preList();
        }
        if (this.right != null) {
            this.right.preList();
        }
    }
}
